package leetcode.editor.cn.q0xx

class Q35 {
    fun searchInsert(nums: IntArray, target: Int): Int {
        return biSearch(nums,0, nums.lastIndex, target)
    }

    fun biSearch(nums: IntArray, startIndex: Int, endIndex: Int, target: Int): Int {
        if (nums[startIndex] > target) {
            return startIndex
        }
        if (nums[endIndex] < target) {
            return endIndex + 1
        }
        val midIndex = (startIndex + endIndex) / 2
        return when {
            nums[midIndex] == target -> {
                midIndex
            }
            nums[midIndex] < target -> {
                biSearch(nums, midIndex, endIndex, target)
            }
            else -> {
                biSearch(nums, startIndex, midIndex, target)
            }
        }
    }
}